package 中等.搜索.广度优先搜索;

import java.util.*;

/**
 * 给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节
 * 点 n-1 的路径并输出（不要求按特定顺序）
 *  graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到
 * 节点 graph[i][j]存在一条有向边）。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/all-paths-from-source-to-target
 */
public class 所有可能的路径_797 {

    public static void main(String[] args) {

    }

    /**
     * 广度优先搜索
     * 因为是无环图，无需标记已经访问过的节点
     */
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> lists = new ArrayList<>();
        Deque<List<Integer>> queue = new ArrayDeque<>();
        queue.addLast(Arrays.asList(0));

        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                List<Integer> curList = queue.pollFirst();

                for (int nextNode : graph[curList.get(curList.size() - 1)]) {
                    List<Integer> nextList = new ArrayList<>();
                    nextList.addAll(curList);
                    nextList.add(nextNode);
                    if (nextNode == graph.length - 1) {
                        lists.add(nextList);
                    } else {
                        queue.addLast(nextList);
                    }
                }
            }
        }

        return lists;
    }

}
